<?php

namespace app\api\controller;

use app\common\controller\Api;

use fast\Random;
use think\Db;

define('INFINITY', 9999999);

class Dijkstra extends Api
{
    // 无需登录的接口,*表示全部
    protected $noNeedLogin = ['*'];
    // 无需鉴权的接口,*表示全部
    protected $noNeedRight = ['*'];

    protected $pathD;

    //http://ela.test/api/dijkstra/test
    public function test()
    {
        $this->success('返回成功');
    }

    function find($node, $list, $next, $a = [])
    {
        if (count($next) == count($list)) {
            return $_GET = [array_merge($next, $a)];
        }
        foreach ($list[$node[strlen($node) - 1]] as $k => $v) {
            foreach ($next as $n => $m) {
                if ($k == $n[strlen($n) - 1]) {
                    unset($list[$node][$k]);
                }
            }
        }
        foreach ($list[$node[strlen($node) - 1]] as $k => $v) {
            $a[$node . $k] = $next[$node] + $v;
        }
        foreach ($a as $k => $v) {
            foreach ($next as $n => $m) {
                if ($k[strlen($k) - 1] == $n[strlen($n) - 1]) {
                    unset($a[$k]);
                }
            }
        }
        foreach ($a as $k => $v) {
            if (!isset($smallest) || $smallest > $v) {
                $smallest = $v;
                $node = $k;
            }
        }
        $next[$node] = $smallest;
        unset($smallest);
        $this->find($node, $list, $next, $a);
    }

    //http://ela.test/api/dijkstra/route0
    public function route0()
    {
        $list = [
            'a' => ['b' => 1, 'c' => 2, 'd' => 3,],
            'b' => ['a' => 1, 'c' => 4, 'e' => 9],
            'c' => ['a' => 2, 'b' => 4, 'd' => 5, 'e' => 6],
            'd' => ['a' => 3, 'c' => 5, 'e' => 8],
            'e' => ['b' => 9, 'c' => 6, 'd' => 8],
        ];
        $this->find('b', $list, ['b' => 0]);


        print_r($_GET);
    }

    //http://ela.test/api/dijkstra/route
    public function route()
    {
        //最简单的算法--- 没有提供路径
        $graphArr = [];
        $Nv = 4; //节点数
        $this->CreateGraph($Nv, $graphArr);//默认的权值都是无穷大 = INFINITY

        $weight = 1;
        $graphArr[1][2] = $weight; // 顶点1 到 顶点2的距离
        $graphArr[2][3] = $weight;
        $graphArr[3][4] = $weight;
        $graphArr[4][1] = $weight;

        $this->Floyd($graphArr);

        //输入节点数组$graphArr，和起点 （1）
        $this->Dijkstra($graphArr, 1, 4);

    }

    function Floyd($graphArr)
    {
        $n = count($graphArr);

        for ($k = 1; $k <= $n; $k++) { // 设 k 为经过的结点
            for ($i = 1; $i <= $n; $i++) {
                for ($j = 1; $j <= $n; $j++) {
                    // 如果经过 k 结点 能使 i 到 j 的路径变短，那么将 i 到 j 之间的更新为通过 k 中转之后的结果
                    if ($graphArr[$i][$j] > $graphArr[$i][$k] + $graphArr[$k][$j]) {
                        $graphArr[$i][$j] = $graphArr[$i][$k] + $graphArr[$k][$j];
                    }
                }
            }
        }
    }

    function CreateGraph($Nv, &$graphArr)
    {
        $graphArr = [];
        for ($i = 1; $i <= $Nv; $i++) {
            for ($j = 1; $j <= $Nv; $j++) {
                if ($i == $j) {$graphArr[$i][$j] = 0;} else { $graphArr[$i][$j] = INFINITY;}
            }
        }
    }

    // $graphArr 节点数组， $origin 起点
    function Dijkstra($graphArr, $origin, $dest)
    {
        $n = count($graphArr);
        $dis = []; // 记录最小值
        $book = []; // 记录结点是否访问过
        // 初始化源点到每个点的权值
        for ($i = 1; $i <= $n; $i++) {
            $dis[$i] = $graphArr[$origin][$i]; // 源点到其它点的默认权值
            $book[$i] = 0; // 所有结点都没访问过
        }

        $book[$origin] = 1; // 源点自身标记为已访问

        $u = 1;
        // 核心算法
        for ($i = 1; $i <= $n - 1; $i++) {
            $min = INFINITY;
            // 找到离目标结点最近的结点
            for ($j = 1; $j <= $n; $j++) {
                // 如果结点没有被访问过，并且当前结点的权值小于 min 值
                if ($book[$j] == 0 && $dis[$j] < $min) {
                    $min = $dis[$j]; // min 修改为当前这个节点的路径值
                    $u = $j; // 变量 u 变为当前这个结点
                }
                // 遍历完所有结点，u 就是最近的那个顶点
            }
            $book[$u] = 1; // 标记 u 为已访问
            for ($v = 1; $v <= $n; $v++) {
                // 如果 [u][v] 顶点小于无穷
                if ($graphArr[$u][$v] < INFINITY) {
                    // 如果当前 dis[v] 中的权值大于 dis[u]+g[u][v]
                    if ($dis[$v] > $dis[$u] + $graphArr[$u][$v]) {
                        // 将当前的 dis[v] 赋值为 dis[u]+g[u][v]
                        $dis[$v] = $dis[$u] + $graphArr[$u][$v];
                    }
                }
            }
            // 最近的结点完成，继续下一个最近的结点
        }

//        for ($i = 1; $i <= $n; $i++) {
//            echo $dis[$i], PHP_EOL; //打印 $origin 到各个节点的最短距离 -- 是ok的
//        }
        echo $dis[$dest];

    }


}


